package me.shan.bit;

/**
 * 描述：一个数组中，只有两种数有奇数个，其余数都是偶数种，求出奇数种的两个数
 *
 * @author liuchuang
 * @date 2021/6/14
 */
public class OddAndEven2 {

    /**
     * 返回数组中所有元素异或的结果
     * @param array 入参数组
     * @return 结果
     */
    public static int eorForArray(int[] array) {
        int a = 0;
        for (int i : array) {
            a ^= i;
        }
        return a;
    }

    public static void main(String[] args) {
        // 假设两种奇数的数分别为a,b
        // 则 eorForArray(array) = a ^ b
        int[] array = {1, 2, 3, 4, 5, 10, 6, 7, 8, 9, 10, 9, 8, 7, 6, 1, 5, 4, 3, 2, 1, 10};
        int eor = eorForArray(array);
        // 使用FindRightOne算法能找出最右边为1的位x，此时eor的x为1，则说明a和b必定是 1,0 或者 0,1
        int x = eor & (-eor);
        // 此时，对数组中第x位为1的数做异或，结果必定为a,b中的一个，就假设为a
        int a = 0;
        for (int i : array) {
            if ((i & x) == x) {
                a ^= i;
            }
        }
        // 因为eor = a ^ b; 所以 b = b ^ a ^ a = eor ^ a
        int b = a ^ eor;
        System.out.println(a + " " + b);
    }
}
